# https://zhuanlan.zhihu.com/p/311598413

def lcs(s1, s2):
    '''
    if s1 == "" or s2 == "":
        return 0
    elif s1[-1] == s2[-1]:
        return lcs(s1[:-1], s2[:-1]) + 1
    else:
        return max(lcs(s1, s2[:-1]), lcs(s1[:-1], s2))
    '''
    dp = [[0]*(len(s2)+1)]*(len(s1)+1)
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            if (s1[i - 1] == s2[j - 1]):
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp




# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    lcs("a", "b")
